\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{lstlisting}
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define int long long
#define ll long long
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
const int N = 5e5 + 10;
struct Edge
{
	int nex , to;
} edge[N << 1];
int head[N] , TOT;
void add_edge(int u , int v)
{
	edge[++ TOT].nex = head[u] ;
	edge[TOT].to = v;
	head[u] = TOT;
}
int n , m , s;
int dep[N] , sz[N] , hson[N] , tp[N] , fa[N] , tot;
void dfs1(int u , int far)
{
	sz[u] = 1 , dep[u] = dep[far] + 1 , fa[u]= far;
	for(int i = head[u] ; i ; i = edge[i].nex)
	{
		int v = edge[i].to;
		if(v == far) continue ;
		dfs1(v , u);
		sz[u] += sz[v];
		if(sz[v] > sz[hson[u]]) hson[u] = v;
	}
}
void dfs2(int u , int far , int top)
{
	tp[u] = top;
	if(!hson[u]) return ;
	dfs2(hson[u] , u , top);
	for(int i = head[u] ; i ; i = edge[i].nex)
	{
		int v = edge[i].to;
		if(v == far || v == hson[u]) continue ;
		dfs2(v , u , v);
	}
}
int lca(int x , int y)
{
	while(tp[x] != tp[y])
	{
		if(dep[tp[x]] < dep[tp[y]]) swap(x , y);
		x = fa[tp[x]];
	}
	if(dep[x] > dep[y]) swap(x , y);
	return x;
}
signed main()
{
	cin >> n >> m >> s;
	rep(i , 2 , n)
	{
		int u , v;
		cin >> u >> v;
		add_edge(u , v) , add_edge(v , u);
	}
	dfs1(s , 0);
	dfs2(s , 0 , s);
	while(m --)
	{
		int u , v;
		cin >> u >> v;
		cout << lca(u , v) << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
